package Day25;

import java.util.Scanner;

/**
 * Creat with IntelliJ IDEA
 * Description
 * User: mamba24
 * Date: 2022-10-16
 * Time: 19:22
 * To BE A Better Person-2020-3-2
 */
public class TestDemo1 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n= sc.nextInt();
            int[] times=new int[n];
        for (int i = 0; i < times.length; i++) {
            times[i]=sc.nextInt();
        }
            for (int i = 0; i < times.length; i++) {
                int fib1 = 1;
                int fib2 = 2;
                int index = times[i];
                int tmep = 0;
                //找到对应的斐波那契数
                while(index > 0){
                    tmep=fib2;
                    fib2+=fib1;
                    fib1=tmep;
                    index--;
                }
                //开始提取数位
                int se=fib1%1000;
                System.out.printf("%04d",se);
            }
        }
        System.out.println();
    }
}
